package meituan;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 跳跃游戏 II https://leetcode-cn.com/problems/jump-game-ii
 * @Author luozhenting
 * @Date 2021/10/15
 **/
public class Jump {
    public int jump(int[] nums) {
        int len = nums.length;
        int INF = Integer.MAX_VALUE / 4;
        int dp[] = new int[len];
        for (int i = 0; i < len; i++) {
            dp[i] = INF;
        }
        dp[0] = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= i + nums[i] && j < len; j++) {
                if (dp[j] > dp[i] + 1) {
                    dp[j] = dp[i] + 1;
                }
            }
        }
        return dp[len - 1];
    }

    @Test
    public void myTest() {
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(this.jump(nums));
    }
}
